#pragma once
#include <sstream>

using namespace std;

template<class T>
class queue
{
private:

	template<class T>
	struct node
	{
		T data;
		node<T> *next;

		node(T data)
		{
			this->data = data;
			this->next = nullptr;
		}
	};

	node<T> *head;
	node<T> *tail;

public:

	queue()
	{
		head = tail = nullptr;
	}

	~queue()
	{
		node<T> *d = nullptr;
		while (head != nullptr)
		{
			d = head;
			head = head->next;
			delete d;
		}
	}

	void push_back(T data)
	{
		node<T> *n = new node<T>(data);
		if (head == nullptr)
			head = tail = n;
		else
			tail = tail->next = n;
	}

	T pop_front()
	{
		if (head == nullptr)
			throw exception("Que<T> is empty, can not pop() from empty queue");
		node<T> *n = head;
		head = head->next;
		if (head == nullptr)
			tail = head;
		T data = n->data;
		delete n;
		return data;
	}

	string str()
	{
		ostringstream oss;
		node<T> *n = head;
		while (n != nullptr)
		{
			oss << n->data << endl;
			n = n->next;
		}
		return oss.str();
	}

	bool is_empty()
	{
		return head == nullptr;
	}

	class iterator
	{
	private:
		node<T> *ptr_;
	public:
		typedef iterator self_type;
		typedef node<T> value_type;
		typedef node<T>* pointer;
		typedef node<T>& reference;
		typedef std::forward_iterator_tag iterator_category;
		typedef int difference_type;

		iterator(pointer ptr) { this->ptr_ = ptr; }

		self_type operator++() 
		{ 
			self_type i = *this; 
			ptr_ = ptr_->next; 
			return i; 
		}

		self_type operator++(int junk) 
		{ 
			ptr_ = ptr_->next; 
			return *this; 
		}

		bool operator==(const self_type& rhs) { return ptr_ == rhs.ptr_; }
		bool operator!=(const self_type& rhs) { return ptr_ != rhs.ptr_; }

		reference operator*() { return *ptr_; }
		pointer operator->() { return ptr_; }
	};

	iterator begin() { return iterator(head); }
	iterator end() { return iterator(nullptr); }
};


